A. Field of the Invention
This invention relates to machine vision, and more particularly, to methods and apparatus for accurately locating circular or curvilinear patterns in a digitized image.
B. Background
Many production machines require automated alignment of objects such as printed circuit boards before processing operations, such as the insertion of integrated circuits can take place. In such applications, machine vision systems can be used to capture and digitize an image of the object to be aligned and analyze that image for a match to a pre-trained "model" of a fiducial or locator target on the object. Typically, search techniques such as correlation search, contour finding or edge detection are used to locate x,y coordinates in the digitized image for a possible match to the pre-trained model. Those results are then sent to the production machine equipment, where the information can be used to move the printed circuit board for proper alignment.
One technique used to improve accuracy in such searching is to decompose the features of the fiducial or target pattern into subfeatures, such as corners or arcs that can be independently located more accurately and whose locations can then be combined to give the location of the whole. The creation of subfeatures is usually done in a separate training step, while searches are conducted at runtime, during production.
Subfeature models of angular fiducial symbols, such as squares, rectangles, crosses and triangles, can be generated using a number of techniques that are simple, fast and accurate. Models of circular or curvilinear fiducials can also be created using existing techniques. However, for reasons of computational efficiency in existing systems and because fiducials are frequently uniform in grey level, the model for a circle or curvilinear symbol is typically a binary model generated from a synthetic image. Calculating grey level values for the boundary locations of a curvilinear object is a more complex task than it is for angular objects.
Previous circle location schemes train four subfeature models at 0, 90, 180, and 270 degrees. Prior techniques can vary in accuracy. If multiple images are taken of the same fiducial (without moving it under the camera), the resulting location reported by the fiducial finder can vary from image to image by as much as 0.25 to 0.5 pixels or pels. Even though this variation is not very severe, it is too great for applications that demand highly accurate position information.
One cause of inaccuracy stems from the binary nature of the typical circular or curvilinear fiducial model. Since curvilinear fiducials cannot be exactly represented by an integral number of binary pels, inaccuracies are built into the model. Computations necessary to determine the fill of a synthetic grey scale circle model are also not trivial. One such method involves the use of integration.
Furthermore, the presence of confusing artifacts near or around the object of interest, non-uniform lighting variations, scale variations, video noise generated in the imaging system, and smearing or obscuration of parts of the symbol all contribute to the difficulty of locating a symbol accurately.
Another significant problem in using subfeature models for curvilinear objects stems from the fact that the x and y axis coordinate positions returned for a particular subfeature model may not be equally likely to indicate a good match. For example, a subfeature model centered at the zero degrees location on the circle's periphery provides quite accurate information about the x axis location of the symbol, but the y axis information is not definitive for that point on the circumference, due to the slow curvature of the circle perimeter. For each subfeature model around the circumference, the x, and y coordinates may vary in their respective information value in a search.
Similarly, in existing search techniques using templates or models, it may happen that the results that match the subfeature model most closely may in fact be positions found as a result of spurious artifacts in the image. For example, a circular fiducial may be represented by four subfeature models. If these four subfeature models are used to search for the fiducial, three of the resulting positions found in the image may actually be part of the fiducial. However, an artifact which is not part of the fiducial may be located by the search technique as a best match for the fourth subfeature. This artifact may be positioned so far away from the other three it could not possibly be part of the fiducial.